#ifndef EXPANSION_GRAPH_SUBGRAPH_ISOMORPHISM_H
#define EXPANSION_GRAPH_SUBGRAPH_ISOMORPHISM_H

#include "expansion_graph.h"
#include "expansion_graph_instance.h"
#include "expansion_graph_instance_ops.h"
#include "pairings.h"

/**
 * Subgraph isomorphism.
 * @param[in] i1 The query graph.
 * @param[in] i2 The database graph.
 * @result @c true if present, @c false otherwise.
 */
template<class V, class E>
  bool subgraph_isomorphism(ExpansionGraph<V, E> *i1, 
                            ExpansionGraph<V, E> *i2)
{
  // Get all possible mappings
  std::multimap<V*, V*> possible_mappings;
  
  if(! get_vertex_mapping(i1, i2, &possible_mappings) ) return false;

  // Initialize the Pairings with all possible mappings
  Pairings<V> possible_seperated_mappings;
  for(typename std::multimap<V*, V*>::iterator i = possible_mappings.begin();
      i != possible_mappings.end();
      i++)
    possible_seperated_mappings.add_pair(i->first, i->second);
  
  // Iterate over each seperated mapping
  std::map<V*, V*> curr_possible_seperated_mapping;
  while(possible_seperated_mappings.get_next_map(&curr_possible_seperated_mapping))
    {
      // Check if constraints are satisfied
      if (check_mapping(i1, i2, &curr_possible_seperated_mapping))
        // Constraints were satisfied by the current possible seperated mapping
        return true;
      else
        // Delete the current possible seperated mapping
        curr_possible_seperated_mapping.erase(curr_possible_seperated_mapping.begin(),
                                              curr_possible_seperated_mapping.end());
    }
  // No seperated mapping satisfied constraints
  return false;
}

#endif //EXPANSION_GRAPH_SUBGRAPH_ISOMORPHISM_H
